/***********************************************************************************/
/* Code license:  GNU General Public License v3                                    */
/* Main page:     https://code.google.com/p/library-cross-platform/                */
/* Issue tracker: https://code.google.com/p/library-cross-platform/issues/list     */
/***********************************************************************************/

#include "findpos.h"

template <class type>
class FindPosBinary : public FindPos<type>
{
  public:
    FindPosBinary();
    virtual ~FindPosBinary();

/*************************************************************************
DESCRIPTION:
 Find element in the input array.
 NOTE: 'in' array MUST be sorted

IN:
  in     - input data.
  length - length of the input data
  val    - this value will be find

RETURN: return position of the found element in the array.
        if result is false then -1 will be returned.
*************************************************************************/
  virtual int findPos(const type *in, int length, const type &val);

/*************************************************************************
DESCRIPTION:
 Find position in the input array. In this position new element must be inserted,
 in this case sorted array will be kept.
 NOTE: 'in' array MUST be sorted

IN:
  in     - input data.
  length - length of the input data
  val    - this value will be find

RETURN: return position which must be used to insert new element.
*************************************************************************/
  virtual int insert2Pos(const type *in, int length, const type &val);

/*************************************************************************
DESCRIPTION:
 Sort input array.

IN:
  in     - input data.
  length - length of the input data

RETURN: if OK return true otherwise false.
*************************************************************************/
  virtual bool sort(type *in, int length);

protected:
  void move_rigth(type *in, int start_index, int end_index);
};




template <class type>
FindPosBinary<type>::FindPosBinary()
{
}

template <class type>
FindPosBinary<type>::~FindPosBinary()
{
}

template <class type>
int FindPosBinary<type>::findPos(const type *in, int length, const type &val)
{
  int lp, rp, mp;

  for(lp = 0, rp = length - 1; lp <= rp;)
  {
    mp = (lp + rp) / 2;
    if(in[mp] == val)
      return mp;
    if(in[mp] > val)
     rp = mp - 1;
    else
     lp = mp + 1;
  }
  return -1;
}

template <class type>
int FindPosBinary<type>::insert2Pos(const type *in, int length, const type &val)
{
  int lp, rp, mp;

  for(lp = 0, rp = length - 1; lp < rp;)
  {
    mp = (lp + rp) / 2;
    if(in[mp] == val)
      return mp;
    if(in[mp] > val)
     rp = mp - 1;
    else
     lp = mp + 1;
  }

  if(val > in[lp])
    return lp + 1;
  return lp;
}

template <class type>
bool FindPosBinary<type>::sort(type *in, int length)
{
  type tmp_val;
  int index  = 1;
  int lindex = 0;

  while(index < length-1)
  {
    lindex = insert2Pos(in, index, in[index]);
    if(lindex == -1)
     return false;

    tmp_val = in[index];
    move_rigth(in, lindex, index);
    in[lindex] = tmp_val;
    index ++;
  }

  return true;
}

template <class type>
void FindPosBinary<type>::move_rigth(type *in, int start_index, int end_index)
{
  while(end_index >= start_index && (end_index - 1) >= 0)
  {
    in[end_index] = in[end_index -1];
    end_index --;
  }
}
